package com.zyk.leetcode;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author zhangsan
 * @date 2021/4/20 17:06
 */
public class C10 {

    // 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
    //
    //'.' 匹配任意单个字符
    //'*' 匹配零个或多个前面的那一个元素
    //所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
    public static boolean isMatch(String s, String p) {
        char[] s1 = s.toCharArray();
        char[] s2 = p.toCharArray();
        return process(s1, s2, s1.length - 1, s2.length - 1);
    }

    private static boolean process(char[] s1, char[] s2, int i, int j) {
        if (i < 0) {
            if (j < 0) return true;
            // ?*?*        首先我当前 s2[j]要为*, 同时我往前走, 有一个不为星后边必须紧挨着一个*就可以返回true.否则都是false
            // case 没做好
            int k = j;
            if(k == s2.length-1 && s2[k--] != '*') return false;
            for (; k >= 0; k--)
                if ((s2[k] != '*' && s2[k + 1] != '*'))
                    return false;
            return true;
        }
        if (j < 0) return false;
        if (s2[j] == '.') {  // .字符可以匹配任意单个字符
            return process(s1, s2, i - 1, j - 1);
        } else if (s2[j] == '*') {
            char pre = j > 0 ? s2[j - 1] : '\0';
            // 1. 我不要这个* 2. 我要, 3.不要,我带着我前边一个直接跳过
            return process(s1, s2, i, j - 2) ||
                    ((pre == '.' || s1[i] == pre) && process(s1, s2, i - 1, j - 2))||
                    ((pre == '.' || s1[i] == pre) && process(s1, s2, i - 1, j));
        } else {
            return s1[i] == s2[j] && process(s1, s2, i - 1, j - 1);    // 普通字符.必须和s1[i] 相等
        }
    }

    public static boolean compareMethod(String s, String p) {
        Pattern r = Pattern.compile(p);
        Matcher m = r.matcher(s);
        return m.find();
    }


    // for test
    public static void main(String[] args) {
//        "aaa"
//        "ab*ac*a"
        String s = "";
        String p = ".*";
        System.out.println(isMatch(s, p));
    }

}
